时间复杂度

在计算机科学中，使用时间复杂度来衡量一个算法的优劣，它可以表示一个算法随着问题规模不断变化的最主要趋势。

大O记法

即算法的时间复杂度随数据量变化的关系曲线，这个关系曲线通常由最高次项决定，当数据量比较高时低次项的影响相对于最高次项就很小，为了方便可以忽略

算法一：$T(n)=n^3\ast 10\Rightarrow T(n)=O(n^3)$

算法二：$T(n)=O(n^2)$

时间复杂度的计算

计算规则

1. 基本操作，认为时间复杂度为O(1)。与问题规模的大小无关，执行次数恒定的算法。
2. 顺序结构，时间复杂度按加法计算
3. 循环结构，时间复杂度按乘法计算
4. 分支结构，时间复杂度取最大值
5. 判断一个算法的效率时，只需要关注操作数量的最高次项，其他次项和常数项可以忽略
6. 没有特殊说明时，所分析的算法的时间复杂度都是指最坏时间复杂度

最优最坏时间复杂度

最优时间复杂度：算法完成最少需要多少基本操作数

最坏时间复杂度：算法完成最多需要多少基本操作数

平均时间复杂度：算法完成工作平均需要多少基本操作数

常见时间复杂度

所消耗的时间从小到大：O(1) < O(n) < $O(n^2)$ <$O(logn)$ < $O(n^3)$, 时间复杂度越低，效率越高。